1. Field of the Invention
This invention relates to computer apparatus and, more particularly, to improvements in arithmetic and logic units of computer processors by which such units may function utilizing less than the typical number of bit positions.
2. History of the Prior Art
Division conducted by a computer is a relatively slow process compared to other mathematical processes. The basic division process requires that the divisor be progressively subtracted from first a dividend and then sequential new interim dividends until a result is reached. These new interim dividends are realized by first shifting each of the bits of the last dividend by one bit to the next higher bit position leaving an empty position at the lowest order bit position, subtracting the divisor from the highest order bits remaining of the dividend to obtain a partial remainder, and concatenating the partial remainder and the lower order unused bits of the original dividend. After the subtraction, the result of the subtraction is evaluated. If the result is positive, the high order bits of the interim dividend were larger than the divisor, a one is recorded for that place of the quotient and placed in the empty lowest order bit position, and a next shift and subtraction occur. If the result is negative, the divisor was larger than the partial remainder, a zero is recorded for the quotient in the lowest order bit position, and the dividend must be restored to its previous condition by adding back the divisor before the next shift and subtraction. In each step, the process requires a subtraction and may require an addition.
This entire process is quite time consuming so various methods of acceleration have been devised. One of these methods is called non-restore division. In this process, the partial remainder is allowed to be either negative or positive so that the interim dividend value does not have to be restored to its prior-to-subtraction value when a negative number results from the subtraction. The process begins with the same shift of the bits of the dividend to the next highest order bit position and a subtraction from the highest order remaining bits of the dividend. If the partial remainder is positive, a one is recorded in the empty bit position, the bits of the interim dividend are each shifted to the next highest order bit position to provide an empty lowest order bit position, and another subtraction occurs. If the result is negative, a shift still occurs, but the divisor is then added back. Since the shift occurs before the divisor is added back, only half the divisor value previously subtracted is added back so the extra step needed to accomplish a restore does not take place. It will be noted that the shift and add by adding only half the value previously subtracted is equivalent to adding the full divisor, shifting, and then subtracting the divisor since the shift causes the subtracted value to be one-half the added value. In fact, the interim dividend is not explicitly restored unless the result of a subtraction is negative at the last step in the division process. The divisor value is simply added back after the next shift to produce a new interim dividend. This process accomplishes division much more rapidly than the restore process because each step requires either a subtraction or an addition but not both. Both the typical restore and the non-restore processes are explained in detail in Cavanaugh, Digital Computer Arithmetic, pp. 236-258.
As may be seen in the Cavanaugh text, the hardware needed to implement the non-restore process of the prior art includes an arithmetic-logic unit (ALU). The ALU used for the operation must be at least one bit larger than the dividend which is to be divided. The carryout from this additional bit position is used to determine the value of the quotient bit for the particular division step and to ascertain what the next operation in the process will be. Thus, if a dividend is a thirty-two bit binary number, a thirty-three bit ALU is required. Similarly, the register holding the partial remainder must be at least one bit longer than the number it is to hold. It has been found that, typically, the greatest number of bit positions required for an ALU used in a computer processor is the number of bits required for the division operation. None of the other operations require the extra number of bit positions which non-restore division has required. Consequently, it is desirable to provide circuitry for accomplishing non-restore division using an ALU which has only the standard number of bits available to other operations. For example, if eight, sixteen, or thirty-two bit dividends are to be divided, then an ALU having the same number of bits as the largest dividend is desirable.